//
// Created by fang.junpeng on 2017/3/30.
//
#include "flow_algori.h"
#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

extern ffun::SmartPtr<Timer> timer;

#define groupNum 6					//定义种群大小
#define NG 1000							//种群的最大繁殖代数

GeneChain geneChain[groupNum];	//定义种群
void geneticAlgorithm(Net& net,Flow& flow,int geneLength){
    srand(time(NULL)); 				//定义随机数生成的种子
    int 		generation=0; 		//当前繁殖的最大代数
    float  	pc=0.90; 					//定义交叉的概率
    float  	pm=0.45; 					//定义变异的概率
    float		pro;

    initFirstGeneration(net,flow,geneLength);			//初代的初始化

    //当停止准则不满足 即繁殖代数没到最大代数 ,继续繁殖
    while(generation<=NG)
    {
        for(int i=0;i<groupNum;i++)
        {
            for(int j=0;j<geneLength;j++)
            {
                geneChain[i].gene[j]=geneChain[i].childGene[j];
            }
        }

        fitnessFunction(net,flow);
        //选择双亲
        for(int i=0;i<groupNum;i++)//8选6?;随机,看落点
        {
            if(i==0)		//保留最优		实现位置待定
                for(int j=0;j<geneLength;j++)	geneChain[0].childGene[j]=geneChain[0].gene[j];
            else
            {
                pro=(float)rand()/(RAND_MAX+1.0);
                if(pro<geneChain[0].rate)
                    for(int j=0;j<geneLength;j++)	geneChain[i].childGene[j]=geneChain[0].gene[j];
                else if(pro>=geneChain[0].rate&&pro<geneChain[1].rate)
                    for(int j=0;j<geneLength;j++)	geneChain[i].childGene[j]=geneChain[1].gene[j];
                else if(pro>=geneChain[1].rate&&pro<geneChain[2].rate)
                    for(int j=0;j<geneLength;j++)	geneChain[i].childGene[j]=geneChain[2].gene[j];
                else if(pro>=geneChain[2].rate&&pro<geneChain[3].rate)
                    for(int j=0;j<geneLength;j++)	geneChain[i].childGene[j]=geneChain[3].gene[j];
                else if(pro>=geneChain[4].rate&&pro<geneChain[5].rate)
                    for(int j=0;j<geneLength;j++)	geneChain[i].childGene[j]=geneChain[4].gene[j];
                else
                    for(int j=0;j<geneLength;j++)	geneChain[i].childGene[j]=geneChain[5].gene[j];
            }
        }
        //***************************杂交算子***************************
        int r=0;
        int z=0;
        for(int j=0;j<groupNum;j++)
        {
            pro=rand()/(RAND_MAX+1.0);
            if(pro<pc)
            {
                ++z;
                if(z%2==0)	Xover(geneChain[r],geneChain[j],geneLength);
                else				r=j;
            }
        }
        //***************************变异算子***************************
        //int pos;
        for(int i=0;i<=groupNum;i++)
        {
            for(int j=0;j<geneLength;j++)
            {
                pro=rand()/(RAND_MAX+1.0);//在[0,1]区间产生随机数
                if(pro<pm)
                {	//在基因链的j位进行变异
                    geneChain[i].childGene[j]=net.conNode[j].feasibleServiceNode[(int)\
						((float)net.conNode[j].feasibleServiceNodeNum*rand()/(RAND_MAX+1.0))];
                }
            }
        }

        generation++;
    }
}

/*********************************************************************
******初始种群初始化函数:length:基因链长度;保证每个基因链都可行*******
*********************************************************************/
void initFirstGeneration(Net& net,Flow& flow,int length)	//初代种群初始化,
{
    for(int i=0;i<groupNum;i++)
    {
        if(0==i)
            for(int j=0;j<length;j++)	geneChain[0].childGene[j]=net.conNode[j].linkNode;
        else
        {
            for(int j=0;j<length;j++)
            {
                geneChain[i].childGene[j]=net.conNode[j].feasibleServiceNode[(int)\
					((float)net.conNode[j].feasibleServiceNodeNum*rand()/(RAND_MAX+1.0))];
            }
        }
    }
}

void fitnessFunction(Net& net,Flow& flow)//定义适合度函数
{
    long tmpFlow;
    double	sum;
    long tmpCost=2*flow.miniCostUntilNow;

    for(int i=1;i<groupNum;i++)	//对后8个基因链依次处理
    {
        //**************根据每个个体基因链初始化服务器列表**************
        net.serviceTableNum=0;
        for(int j=0,k;j<net.consumNodeNum;j++)
        {
            if(j!=0)
            {
                k=0;
                while(k<net.serviceTableNum)
                {
                    if(net.serviceTable[k]==geneChain[i].gene[j])	goto	ignore;
                    k++;
                }
            }
            net.serviceTable[net.serviceTableNum]=geneChain[i].gene[j];
            net.serviceTableNum++;
            ignore:	;
        }

        //**********************最小费用最大流处理**********************
        flow.minCost=net.serviceTableNum*net.serverPrice;//操作之前应完成服务器节点的更新
        for(int j=0;j<net.nodeNum;j++)//重新初始化带宽capacity
        {
            for(int k=0;k<net.node[j].linkedNum;k++)
                net.node[j].capacity[k]=net.node[j].state[k];
        }

        net.freeSuperSource();
        net.insertSuperSource(net.serviceTable,net.serviceTableNum);
        tmpFlow=minCostMaxFlow(net,flow,net.nodeNum+1,net.nodeNum);
        //****************************检查更新*************************
        if(flow.MaxFlow==tmpFlow)
        {
            if(flow.minCost<flow.miniCostUntilNow)
            {
                flow.miniCostUntilNow=flow.minCost;//更新最优费用
                cout<<"miniCostUntilNow:"<<flow.miniCostUntilNow<<endl;

                //更新最优路径
                for(int k=0;k<flow.bestPathNum;k++)//清空原来的
                    while(!flow.bestPath[k].empty())	flow.bestPath[k].pop();

                for(int k=0,v;k<flow.FeasiblePathNum;k++)//更新
                {
                    v=0;
                    while(flow.FeasiblePath[k][v] != -1)
                    {flow.bestPath[k].push(flow.FeasiblePath[k][v]);v++;}
                }
                flow.bestPathNum=flow.FeasiblePathNum;

                //更新最优基因链
                swapArray(geneChain[0],geneChain[i],net.consumNodeNum);
                swap(geneChain[0].cost,geneChain[i].cost);
            }
            geneChain[i].cost=flow.minCost;//minCost全局变量,记录最小费用流的费用
        }
        else
        {
            geneChain[i].cost=flow.miniCostUntilNow;			//不满足最大流
        }
    }
    //************************计算适应度*****************************

    sum=0.0;
    //因为总费用越小越优，这里做了下处理
    for(int i=0;i<groupNum;i++)	sum+=tmpCost-geneChain[i].cost;
    for(int i=0;i<groupNum;i++)
    {
        if(0==i)
            geneChain[i].rate=geneChain[i].cost/sum;
        else
            geneChain[i].rate=geneChain[i].cost/sum+geneChain[i-1].rate;
    }
}

/*********************************************************************
***********基因杂交函数:根据选定的双亲，完成基因的交叉操作************
*********************************************************************/
void Xover(GeneChain& a,GeneChain& b,int& geneLength)
{
    int pos; 				//随机生成杂交点 即第几个分量进行相互交换
    int tmp;				//用于交换的暂存变量
    pos=(int)(geneLength*rand()/(RAND_MAX+1.0)); //在n个分量中，随机确定第pos个分量
    for(int i=0;i<pos;i++)
    {
        tmp=a.childGene[i];
        a.childGene[i]=b.childGene[i];
        b.childGene[i]=tmp;
    }
}

void swapArray(GeneChain& a,GeneChain& b,int length)
{
    int tmp;
    for(int i=0;i<length;i++)
    {
        tmp=a.gene[i];
        a.gene[i]=b.gene[i];
        b.gene[i]=tmp;
    }
}


int		dis[1002];				//spfa函数中到各点最短距离的记录数组
int 	pre[1002];				//spfa函数中前向节点的记录数组
bool	ifVisited[1002];	//spfa函数中记录节点是否访问过
int minCostMaxFlow(Net& net,Flow& flow,int s,int t){
    int	count;
    int max_flow = 0; // 总流量
    int minflow;

    flow.reset_path();

    while(spfa(net,flow,s,t))
    {
        minflow = INF + 1;
        for(int i = pre[t],j = t;i != s;i = pre[i])
        {
            for(int k=0;k<net.node[i].linkedNum;k++)
            {
                if(net.node[i].linkedNode[k]==j)
                {
                    if(net.node[i].capacity[k] < minflow)
                    {
                        minflow = net.node[i].capacity[k];
                    }
                }
            }
            j=i;
        }
        max_flow += minflow;
        flow.minCost += dis[t] * minflow;

        //以下为记录路径等信息
        flow.FeasiblePath[flow.FeasiblePathNum][0]=minflow;//加入本条路的流量
        flow.FeasiblePath[flow.FeasiblePathNum][1]=net.indexOfconNode[pre[t]];//加入消费节点
        count=2;
        for(int i = pre[t],j = t;i != s;i = pre[i])
        {
            for(int k=0;k<net.node[i].linkedNum;k++)
            {
                if(net.node[i].linkedNode[k]==j)
                {
                    net.node[i].capacity[k] -= minflow;
                    flow.FeasiblePath[flow.FeasiblePathNum][count]=i;
                    count++;
                }
            }
            j=i;
        }

        flow.FeasiblePathNum++;
    }
    return	max_flow;// 最大流
}

bool spfa(Net& net,Flow& flow,int s,int t)
{
    timer->watch_event();//查看事件,若时间到了,则运行事件
    int u,v;
    queue<int>q;

    //spfa初始化
    for(int i=0;i<net.nodeNum+2;i++)  pre[i]=-1;
    for(int i=0;i<net.nodeNum+2;i++)  dis[i]=INF;
    for(int i=0;i<net.nodeNum+2;i++)  ifVisited[i]=false;


    dis[s] = 0;
    ifVisited[s] = true;
    q.push(s);          //superSource入队

    //spfa初始化，或重写数组内一些数据，均放在spfa函数外
    while(!q.empty())
    {
        u = q.front();
        q.pop();
        ifVisited[u] = false;//release from queue q

        for(int i = 0; i < net.node[u].linkedNum; i++)
        {
            v = net.node[u].linkedNode[i];
            if((net.node[u].capacity[i]>0) && (dis[v] > dis[u]+net.node[u].cost[i]))
            {
                dis[v] = dis[u] + net.node[u].cost[i];
                pre[v] = u;				//用于前向搜索
                if(!ifVisited[v])
                {
                    q.push(v);
                    ifVisited[v]=true;
                }
            }
        }
    }
    if(dis[t] == INF)	return false;

    return true;
}